package com.yx;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yx
 * @date 2025-04-09 16:01
 * @description: 二分查找法
 */
public class BinarySearchDemo {

    /**
     * 二分查找(双闭区间)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找(左闭右开区间)
     * 定义为 [0, 𝑛) ，即左边界包含自身，右边界
     * 不包含自身。在该表示下，区间 [𝑖, 𝑗) 在 𝑖 = 𝑗 时为空。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchLCRO(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {//𝑖 = 𝑗 时为空
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {//此情况说明 target 在区间 [m+1, j) 中
                l = m + 1;
            } else { //此情况说明 target 在区间 [i, m) 中
                r = m;
            }
        }
        return -1;
    }

    /**
     * 二分查找插入点
     * 无重复元素情况
     * 数组存在target，则索引为target所在的索引
     * 数组不存在target，则索引为l指针
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchInsertionSimple(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l;//未找到 target ，返回插入点 i
    }

    /**
     * 二分查找插入点
     * 存在重复元素
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchInsertion(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                r = m - 1;//首个小于target的元素在[l, m-1]区间
            } else if (nums[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    /**
     * 二分查找边界
     * 查找左边界
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchLeftEdge(int[] nums, int target) {
        int i = binarySearchInsertion(nums, target);
        if (i == nums.length || nums[i] != target) {//i索引越界 或者 未找target元素
            return -1;
        }
        return i;
    }

    /**
     * 二分查找边界
     * 查找右边界
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchRightEdge(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                l = m + 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (r == -1 || nums[r] != target) {
            return -1;
        }
        return r;
    }

    /**
     * 二分查找边界
     * 查找右边界-复用左边界版
     * 查找最右target 等价于 查找最左 （target+1）
     * <p>
     * 同理可以将查找边界改为查找元素
     * ‧ 查找最左一个 target ：可以转化为查找 target - 0.5 ，并返回指针 𝑖 。
     * ‧ 查找最右一个 target ：可以转化为查找 target + 0.5 ，并返回指针 𝑗 。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearchRightEdge1(int[] nums, int target) {
        int i = binarySearchInsertion(nums, target + 1);
        int j = i - 1;
        if (j == -1 || nums[j] != target) {
            return -1;
        }
        return j;
    }

    /**
     * 我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。
     */

    /**
     * 给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元
     * 素，并返回它们的数组索引。返回任意一个解即可。
     */

    /**
     * 两数之和
     * 线性查找：以时间换空间
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSumBruteForce(int[] nums, int target) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 两数之和
     * 哈希优化
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSumHash(int[] nums, int target) {
        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 5, 6, 6, 6, 6};
        int i = binarySearchRightEdge1(nums, 6);
        System.out.println("找到对应的元素坐标:" + i);

        int[] ints = twoSumHash(nums, 5);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

}
